package com.chenxys.algorithm.leetcode;

/**
 * <p>
 *      <a href="https://leetcode.cn/problems/maximum-rows-covered-by-columns/description/">被列覆盖的最多行数</a><br/>
 *      给你一个下标从0开始、大小为mxn的二进制矩阵matrix；另给你一个整数numSelect，表示你必须从matrix中选择的不同列的数量。<br/>
 * 　　   如果一行中所有的1都被你选中的列所覆盖，则认为这一行被覆盖了。<br/>
 * 　　   形式上，假设s={c1,c2,....,cnumSelect}是你选择的列的集合。对于矩阵中的某一行row，如果满足下述条件，则认为这一行被集合s覆盖：<br/>
 * 　　   对于满足matrix[row][col]==1的每个单元格matrix[row][col]（0<=col<=n-1），col均存在于s中，或者row中不存在值为1的单元格。<br/>
 * 　　   你需要从矩阵中选出numSelect个列，使集合覆盖的行数最大化。<br/>
 * 　　   返回一个整数，表示可以由numSelect列构成的集合覆盖的最大行数。<br/>
 *      例: <br/>
 *          输入：matrix=[[0,0,0],[1,0,1],[0,1,1],[0,0,1]],numSelect=2<br/>
 *          输出：3<br/>
 *          解释：<br/>
 * 　　          选择s={0,2}。<br/>
 * 　　           -第0行被覆盖，因为其中没有出现1。<br/>
 * 　　           -第1行被覆盖，因为值为1的两列（即0和2）均存在于s中。<br/>
 * 　　           -第2行未被覆盖，因为matrix[2][1]==1但是1未存在于s中。<br/>
 * 　　           -第3行被覆盖，因为matrix[2][2]==1且2存在于s中。<br/>
 * 　　   因此，可以覆盖3行。<br/>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.leetcode
 * @date 2024/1/4 14:53
 * @Copyright ©
 */
@SuppressWarnings("all")
public class LeetCode2397 {
    /**
     * <p>
     *     被列覆盖的最多行数
     * </p>
     * @param matrix 二进制矩阵
     * @param numSelect 必须选择的列的个数
     * @return 被列覆盖的最多行数
     */
    public static int maximumRows(int[][] matrix, int numSelect) {
        // 行数
        int m = matrix.length;
        // 列数
        int n = matrix[0].length;
        // 共m行, 所以数组长度为m,保存每行的十进制结果
        int[] mask = new int[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // mask[i] += matrix[i][j] << (n - j - 1); 将当前行代表的十进制数计算出来
                mask[i] += matrix[i][j] << (n - j - 1);
            }
        }

        // 保存最后结果
        int res = 0;
        // 当前行
        int cur = 0;
        // 总行数
        int limit = (1 << n);
        while (++cur < limit) {
            // bitCount统计这个数的二进制位有多少个1,如5 返回2
            // 如果当前十进制数的二进制1个数 和 numSelect的个数不一样,继续
            if (Integer.bitCount(cur) != numSelect) continue;
            // 当前覆盖行的数量
            int tmp = 0;
            // 个数一致,
            for (int i = 0; i < m; i++) {

                if ((mask[i] & cur) == mask[i]) ++tmp;
            }
            // 维护最大值
            res = Math.max(res, tmp);
        }
        return res;
    }


    /**
     * <p>
     *     被列覆盖的最多行数
     * </p>
     * @param matrix 二进制矩阵
     * @param numSelect 必须选择的列的个数
     * @return 被列覆盖的最多行数
     */
    public static int checkMaximumRows(int[][] matrix, int numSelect) {
        // 行数
        int m = matrix.length;
        // 列数
        int n = matrix[0].length;
        // 共m行, 所以数组长度为m,保存每行的十进制结果
        int[] mask = new int[m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // mask[i] += matrix[i][j] << (n - j - 1); 将当前行代表的十进制数计算出来
                mask[i] += matrix[i][j] << (n - j - 1);
            }
        }
        int res = 0;
        int cur = (1 << numSelect) - 1;
        int limit = (1 << n);
        while (cur < limit) {
            int t = 0;
            for (int j = 0; j < m; j++) {
                if ((mask[j] & cur) == mask[j]) {
                    ++t;
                }
            }
            res = Math.max(res, t);
            int lb = cur & -cur;
            int r = cur + lb;
            cur = ((r ^ cur) >> Integer.numberOfTrailingZeros(lb) + 2) | r;
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] matrix = {{0, 0, 0}, {1, 0, 1}, {0, 1, 1}, {0, 0, 1}};
        maximumRows(matrix, 2);
    }

}
